package day_2022_12_to_3.day;

import java.util.HashMap;
import java.util.Map;

/**
 * @author haomin
 * @date 2022/12/09 22:13
 **/
public class Day12_9_Review {
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < nums.length; ++i) {
                if(!map.containsKey(nums[i])) map.put(target - nums[i], i);
                else return new int[]{i, map.get(nums[i])};
            }
            return new int[0];
        }
    }

    class Solution2 {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int pre = 0;
            ListNode dummyHead = new ListNode(-1);
            ListNode cur = dummyHead;
            while(l1 != null || l2 != null) {
                int sum = 0;
                if(l1 != null) sum += l1.val;
                if(l2 != null) sum += l2.val;
                sum += pre;
                pre = sum / 10;
                sum = sum % 10;
                cur.next = new ListNode(sum);
                cur = cur.next;

                if(l1 != null) l1 = l1.next;
                if(l2 != null) l2 = l2.next;
            }
            if(pre != 0) cur.next = new ListNode(pre);
            return dummyHead.next;
        }
    }

    class Solution3 {
        public int lengthOfLongestSubstring(String s) {
            if(s.length() <= 1) return s.length();
            int ans = 0, l = 0, r = 1;
            while(l < s.length() && r < s.length()) {
                while(r < s.length() && !s.substring(l, r).contains(s.charAt(r) + ""))  r++;
                ans = Math.max(r - l, ans);
                if(r == s.length()) break;

                while(l < s.length() && s.substring(l, r).contains(s.charAt(r) + "")) l++;
            }
            return ans;
        }
    }

    class Solution3_Ⅱ {
        public int lengthOfLongestSubstring(String s) {
            if(s.length() == 0) return 0;
            int ans = 0, preIndex = 0;
            Map<Character, Integer> map = new HashMap<>();
            for(int i = 0; i < s.length(); ++i) {
                if(map.containsKey(s.charAt(i))) {
                    preIndex = Math.max(preIndex, map.get(s.charAt(i)) + 1);
                }
                ans = Math.max(ans, i - preIndex + 1);
                map.put(s.charAt(i), i);
            }
            return ans;
        }
    }

    class Solution4 {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int totalLen = nums1.length + nums2.length;
            int mid = totalLen / 2;
            int k = 0, i = 0, j = 0, m = nums1.length, n = nums2.length;
            int m1 = 0, m2 = 0;
            while(k <= mid && (i < m || j < n)) {
                m1 = m2;
                if(i == m || (i != m && j != n && nums2[j] < nums1[i]))
                    m2 = nums2[j++];
                else m2 = nums1[i++];
                k++;
            }
            return totalLen % 2 == 1 ? (double) m2 : (double) (m1 + m2) / 2;
        }
    }
}